1. Field of the Invention
This invention relates generally to computer networks and, more particularly, to distributing routing information associated with routing protocols used in a computer network.
2. Background Information
A computer network is a geographically distributed collection of interconnected communication links for transporting data between nodes, such as computers. Many types of computer networks are available, with the types ranging from Local Area Networks (LANs) to Wide Area Networks (WANs). The nodes typically communicate by exchanging discrete frames or packets of data according to pre-defined protocols. In this context, a protocol consists of a set of rules defining how the nodes interact with each other.
Computer networks may be further interconnected by an intermediate node, called a router, to extend the effective “size” of each network. Since management of a large system of interconnected computer networks can prove burdensome, smaller groups of computer networks may be maintained as autonomous systems or routing domains. An autonomous system is defined as a set of routers under a single administrative authority, that use an interior gateway protocol (IGP) and common metrics to route packets within the autonomous system and an exterior gateway protocol (EGP) to route packets to other autonomous systems.
An IGP is a routing protocol that, inter alia, distributes routing information to the routers within an autonomous system. IGPs are often configured to calculate efficient routes and recalculate them quickly after certain events, such as a network topology change. Examples of IGPs include the Routing Internet Protocol (RIP), Open Shortest Path First (OSPF) and Enhanced Interior Gateway Routing Protocol (EIGRP). An EGP, on the other hand, is a routing protocol that, inter alia, distributes routing information to routers that interconnect autonomous systems. EGPs are typically configured to express particular routing policies and aggregate routing information associated with a collection of autonomous systems. Examples of an EGP is the Border Gateway Protocol (BGP) which is described in detail in A Border Gateway Protocol 4 (BGP-4), Request For Comments (RFC) 1771, by Y. Rekhter, et al., and the Multiprotocol BGP (MBGP), which is described in detail in Multiprotocol Extensions for BGP-4, Request For Comments (RFC) 2858, by T. Bates, et al., both of which are available from the Internet Engineering Task Force (IETF) at http://www.ietf.org and are hereby incorporated by reference as though fully set forth herein.
BGP is an Internet Protocol (IP) version 4 (IPv4) based inter-domain routing protocol that supports classless inter-domain routing, allows the aggregation of routes, and provides for policy-based routing. MBGP is an extension of BGP that supports other protocols in addition to IPv4 including IP version 6 (IPv6), IP Multicast, Virtual Private Network version 4 (VPNv4), and Virtual Private Network version 6 (VPNv6). Both BGP and MBGP use a reliable transport protocol, such as the Transmission Control Protocol (TCP), to distribute routing information in the form of update messages.
Routers running IGPs and EGPs are typically configured to maintain routing tables, transmit routing update messages and render routing decisions based on various routing metrics. Specifically, each router maintains routing information that lists routes or paths to particular destinations in the network. Periodic refreshing of the routing information occurs depending on the routing protocol. Moreover, routers residing in the autonomous systems exchange routing information under various circumstances. For example, when a BGP router initially connects to the network, the peer routers exchange the entire contents of their routing tables, which contain the routing information. Likewise when the topology of the network changes, routing tables often are recalculated and the contents of these recalculated tables are communicated to the peer routers through one or more update messages.
A network of routers is considered converged when all the routers in the network agree on the network's topology, i.e., the routers agree on the optimal routes to each destination in the network. Generally speaking, most IGPs are based on one of two types of distributed routing algorithms: link-state or distance vector. The routing information that is exchanged between peers and the method employed to reach convergence often depends on the type of distributed routing algorithm employed by the protocol.
Distance vector protocols, such as RIP, often include a vector (list) of distances (hop counts or other metrics) associated with a route in the routing information that is distributed. Moreover, distance vector protocols utilize a distributed computation approach to calculating the route to each destination; that is, each router separately calculates the best path to each destination. After selecting the best path, the router sends distance vectors to its neighbors to notify them of the reachability of the destination and the corresponding metrics associated with the path. The neighbors use this information, to calculate the best path to each of the destinations and then notify their neighbors of the available path they've selected to reach the destination. Upon the receipt of messages, the router might determine that a better path exists via an alternative neighbor. The router will again notify its neighbors of its selected paths to reach each destination. This cycle continues until all the routers have converged upon a common understanding of the best paths to reach each destination.
Link-state protocols, such as OSPF, utilize a replicated distributed database model to maintain link-state information. Link-state protocols work on the basis that routers exchange information elements, called link states, which carry information about links and nodes in the routing domain. Routers that run link-state protocols do not exchange routing tables as distance vectors protocols do. Rather, they exchange information about connections to adjacent neighbors and networks, and include metric information associated with each connection. Each router in the network generates the link state that describes it and its connections to the adjacent routers. The router also generates a list of metrics corresponding to the connection with each adjacent router. This information is then distributed by the router throughout the network in one or more update messages, often called Link State Advertisements (LSAs), until all routers in the routing domain have received the routing information from each of the other routers. Each router then uses the information to construct a routing table that represents all the routes for all the destinations in the routing domain.
EGP protocols, such as BGP and MBGP, on the other hand, often employ a path vector routing algorithm, which maintains a traceroute-like path vector that indicates how a route was created and propagated. These protocols often exchange routing information using a transport protocol such as the TCP protocol. A router running an EGP protocol typically exchanges routing information with its neighboring peer routers at start-up time. Periodic refreshing of the routing information, however, is generally not performed. The routing protocol may learn of multiple paths to the same destination from its peers and often chooses a path by selecting the best path among the multiple paths. The chosen path is then typically maintained in its routing information as the path to that destination.
In systems where the amount of routing information is quite large, a router may need to send a large number of packets in order to disseminate the routing information to other routers in the network. A router receiving these update messages often processes the routing information on a first-come-first-served basis; thus routing information received in earlier messages often converges ahead of routing information received in later messages. A system containing many thousands of routes may take on the order of minutes to completely converge, thus causing later transmitted routes to experience an inordinate amount of downtime due to convergence delays. In systems where network downtime is strictly governed, such as systems subject to Service Level Agreements (SLAs), such outages may be unacceptable.